package com.leetcode.algorithm.y22.m07.w5;

import com.leetcode.algorithm.common.ListNode;

/**
 * 剑指 Offer II 078. 合并排序链表
 * 
 * https://leetcode.cn/problems/vvXgSW/
 * 
 * @author jie.deng
 *
 */
class QuestionOffer2078Solution02 {

	public ListNode mergeKLists(ListNode[] lists) {
		ListNode sentinel = new ListNode();
		ListNode cur = sentinel;
		while (true) {
			ListNode min = null;
			int minIdx = -1;
			for (int i = 0; i < lists.length; i++) {
				ListNode tmp = lists[i];
				if (tmp != null) {
					if (min == null || tmp.val < min.val) {
						min = tmp;
						minIdx = i;
					}
				}
			}
			if (min == null) {
				break;
			}
			cur.next = new ListNode(min.val);
			lists[minIdx] = lists[minIdx].next;
			cur = cur.next;
		}

		return sentinel.next;
	}

}